火柴拼图

[编程题]火柴拼图

热度指数：1101 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹有n根火柴，她想用这些火柴去拼正三角形或者正四边形。牛妹想让最后拼出的总面积尽可能大的，请你帮帮她。

返回一个Vector，Vector中存有两个数字。

其中最大面积 $S=Vector[0]*\sqrt3/4+Vector[1]$ 。

示例1

输入

4,[1,1,1,1]

输出

[0,1]

说明

构成一个边长为1的正四边形面积总和最大，值为1。所以Vector[0]=0，Vector[1]=1

备注:

Stick[i]表示第i根火柴的长度，一共有n根火柴

算法知识视频讲解

Python 3

蒙太奇在秋天

总算是写出来了，就是凡是数目大于等于4就要先拼正方形；凡是数目对4取余数为3的，就要把余数拿来拼三角形

class Solution:
    def MaxArea(self , n , Stick ):
        # write code here
        # 存放两个输出量，即边长平方
        vector = [0,0]
        # 连三角形都不够拼的
        if n < 3:
            return vector
        # 从大到小按顺序排好，这点很重要
        Stick.sort(reverse = True)
        i = 0
        while i < n:
            # 统计该长度火柴有几根
            numi = Stick.count(Stick[i])
            # 凡是numi>=4就要拼正方形，因为面积大
            # *(numi//4)是关键一点，保证了不足4个的火柴被排除
            vector[1] += (Stick[i]**2) * (numi//4)
            # 拼完正方形剩3根的，或本身就只有3根，拿来拼三角形
            if numi%4 == 3:
                vector[0] += Stick[i] ** 2
            # 下一个数
            i += numi
        return vector

发表于 2021-09-29 15:24:59 回复(0)